Digital cross-connect communications network devices, such as the 1631 SX manufactured by Alcatel Network Systems, Inc., are designed to make connections between input gates on input switches and output gates on output switches. Known designs for such cross-connect devices make use of matrices to connect the input gates to the output gates. To limit the physical space and manufacturing costs of the matrices, designers seek to minimize the number of cross-connects in the matrix. This objective becomes more complicated as market demands for communications services increase. In particular, as network devices address larger markets, the devices must service more and more input and output signals. These factors exacerbate the space and cost limitation problems even more for communications matrix devices.
One matrix configuration that uses a minimal number of matrix cross-connects for a given number of input gates and output gates and that provides a potentially optimal solution is known as a "rearrangeable" matrix. For the rearrangeable matrix, the number of center stage switches must equal or exceed the number of input gates on each switch of the matrix. In a rearrangeable matrix, there exists a set of conditions such that, although the device does not use all input gates and all output gates, an attempt to use an idle input gate and an output gate is prohibited because existing connections block the signal flow through the matrix. This may happen, for example, if existing connections already occupy at least one link in every possible path between the input and output gates in question.
In a rearrangeable network, it is always possible to unblock a flow path from an idle input gate to an idle output gate by moving existing connections in the network. The term "rearrangeable," therefore, describes the property that for a given state of a network and any given idle pair of input and output gates, the existing connections of the matrix may be reassigned to new paths, if necessary, to connect the idle pair.
Existing methods and systems for connecting inputs to outputs in rearrangeable matrices generally use a standard rearrangement technique that determines which cross-connects of the matrix to rearrange to permit a signal to flow. N. C. Paull in "Reswitching of Connection Networks," The Bell System Technical Journal, May, 1962, pp. 833-856, describes this known method for unblocking a rearrangeable matrix. This method (hereinafter referred to as Paull's Method) suffers from a major limitation. Paull's Method requires breaking some of the cross-connects and making some other of the cross-connects to rearrange matrix. This procedure takes time and results in undesirable service delays or interruptions during matrix rearrangement.
It is an object of the present invention, therefore, to provide a method and system that selects an optimal connection path for a rearrangeable communications matrix that permits immediate connection of idle input gates to idle output gates. The present invention achieves this object with a minimal amount of additional circuitry and avoids the service delays and interruptions of known connection path selection methods and systems that cannot immediately select an optimal connection configuration.
It is also an object of the present invention to provide a method and system that finds an optimal connection path or configuration through a communications matrix that uses a set of five matrices, the first of which represents the assignment of input gates of input switches to center stage switches using an input array of values that associate center stage switches to the input stage switches and input gates of the input switches, the second of which represents center stage switch connections by a center stage array of values that associate center stage switches with input stage switches and output stage switches, the third of which represents output stage connections by an output stage array having values that associate output stages switches with output gates and center stage switches the fourth of which represents the idle links from the input stage switches to the center stage switches by an idle input link array having values that indicate the idle status of the links, and the last of which represents the idle links from the center stage switches to the output stage switches by an idle output link array having values that indicate the idle status of the links, and then using these five arrays the method and system perform a process called "pumping" these arrays to determine an optimal center stage switch having an idle connection between a predetermined input gate and a predetermined output gate and then sets an associated input stage array value and output stage array value to indicate the optimal center stage switch for the connection configuration.